package editor.cn;

//Given an array of strings strs, group the anagrams together. You can return th
//e answer in any order. 
//
// An Anagram is a word or phrase formed by rearranging the letters of a differe
//nt word or phrase, typically using all the original letters exactly once. 
//
// 
// Example 1: 
// Input: strs = ["eat","tea","tan","ate","nat","bat"]
//Output: [["bat"],["nat","tan"],["ate","eat","tea"]]
// Example 2: 
// Input: strs = [""]
//Output: [[""]]
// Example 3: 
// Input: strs = ["a"]
//Output: [["a"]]
// 
// 
// Constraints: 
//
// 
// 1 <= strs.length <= 104 
// 0 <= strs[i].length <= 100 
// strs[i] consists of lower-case English letters. 
// 
// Related Topics 哈希表 字符串 
// 👍 542 👎 0

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class GroupAnagrams{
    public static void main(String[] args) {
        Solution solution = new GroupAnagrams().new Solution();
        String[] strs = {"abets","bead","remain","betas","abed","baste","airline","leading","beast","dealing","beats","airmen","marine","single","bade","aligned"};
        List<List<String>> lists = solution.groupAnagrams(strs);
        for (List<String> list : lists) {
            for (String s : list) {
                System.out.print(s);
                System.out.print("        ");
            }
            System.out.println();
        }
    }

//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        ArrayList<List<String>> results = new ArrayList<>();
        int count = 0;
        int temp = 0;
        boolean flag = false;
        boolean flag2 = true;
        for (String str : strs) {
            char[] ones = str.toCharArray();
            char result=0;
            for (List<String> list : results) {
                char[] chars = list.get(0).toCharArray();
                result = 0;
                if (chars.length == ones.length) {
                    Arrays.sort(chars);
                    Arrays.sort(ones);
                    for (int i = 0; i < chars.length; i++) {
                        if (ones[i] != chars[i]) {
                            result = 1;
                            break;
                        }
                    }
                    if (result == 0) {
                        list.add(str);
                        count++;
                        break;
                    }
                } else {
                    if (ones.length == 0) {
                        if (flag2) {
                            temp = count;
                        }
                        flag = true;

                    }
                    result = 1;

                }
            }
            if (result!=0||results.size()==0){
                if (flag) {
                    if (flag2) {
                        ArrayList<String> inner = new ArrayList<>();
                        inner.add(str);
                        results.add(inner);
                        flag2 = false;
                    } else {
                        List<String> list = results.get(temp-1);
                        list.add(str);
                    }
                    flag = false;
                } else {
                    ArrayList<String> inner = new ArrayList<>();
                    inner.add(str);
                    results.add(inner);
                    count++;
                }
            }
        }
        return results;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}